package array;

/**
 * @Author wangtengyu
 * @Create 2018-09-10-15:27 求递增排序的数组的旋转后的数组元素中的最小值，例如{1,2,3,4,5} 旋转后为3,4,5,1,2
 * 思路：定义两个指针head，tail，一个指向头，一个指向尾。再定义一个指针millde指向中间元素 如果middle指向的值大于head指向的值，则证明middle在前面的序列中。head指向middle
 * 如果middle指向的值小于tail指向的值，则证明middle在后面的序列中。tail指向middle
 *
 * 当head和tail是相邻的时候，最小值就是tail所指向的值
 *
 * 特殊情况 1.{1,2,3,4,5} 反转后为{1,2,3,4,5}  判断head所指的值如果小于tail所指的值，说明数组是有序的，返回head所指的值 2、{0,1,1,1,1}
 * 反转后为{1,0,1,1,1} 无法判断middle在前面的序列还是后面的序列
 */
public class RotateArray {


  public int findMinValue(int[] array) {
    if (array == null || array.length <= 0) {
      return -1;
    }

    int head = 0;
    int tail = array.length - 1;
    int middle = (head + tail) / 2;

    //针对特殊情况1的判断 {1,2,3,4,5}
    if (array[head] < array[tail]) {
      return array[head];
    }

    //针对特殊情况2的判断 {1,0,1,1,1}
    if (array[head] == array[middle] && array[tail] == array[middle]) {
      int min = array[head];
      for (int i = 1; i < array.length; i++) {
        if (min < array[i]) {
          min = array[i];
        }
      }
      return min;
    }

    //正常情况的判断
    while ((tail - head) != 1) {
      if (array[middle] >= array[head]) {
        head = middle;
      } else {
        tail = middle;
      }
      middle = (head + tail) / 2;
    }
    return array[tail];
  }


  public static void main(String[] args) {
    int[] array = new int[]{3, 4, 5, 1, 2};
    int[] array2 = new int[]{1, 2, 3, 4, 5};
    int[] array3 = new int[]{1, 0, 1, 1, 1};

    RotateArray rotateArray = new RotateArray();
    System.out.println(rotateArray.findMinValue(array));
    System.out.println(rotateArray.findMinValue(array2));
    System.out.println(rotateArray.findMinValue(array3));
  }
}
